package leetcode_core.leetcode_1;

public class FindTargetSumWayByDpTable {
    private int helper(int[] nums,int target){//0-1背包问题
        //1.定义dp数组,dp[i][j]:前i个物品和j的背包容量
        int[][] dp = new int[nums.length+1][target+1];
        //2.写出base-case
        //2.1 当i等于0的时候,找不到一组合适的方法
        for(int j=0;j<=target;j++){
            dp[0][j] = 0;
        }
        dp[0][0] =1;
        //3.确定遍历方向,由DP-table可知初始化的是第零行和第零列的元素,因此从(1,1)开始遍历到后边即可
        for(int i = 1;i<=nums.length;i++){
            for(int j = 0;j<=target;j++){
                if(j-nums[i-1] <0){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j]+dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[nums.length][target];
    }

    public int findTargetSumWays(int[] nums, int target) {
        //sum(A) =(target+sum(nums))/2;
        int sum = 0;
        for (int num : nums) {
            sum+=num;
        }
        int sumADouble = target+sum;//如果是奇数,那么就无法找到一组合适的划分方法,直接返回0
        //如果全部正数的num加起来都到不了target,我还要给它赋值负数呢,这时候怎么可能会有解?
        if( sum < target || sumADouble%2==1 ){
            return 0;
        }
        return helper(nums,Math.abs((sum+target)/2));
    }


}
